package leetcode;

/**
 * @author Liangyaoyun
 */
public class leetCode493 {
    public int findReversePairs(int[] num,int left,int right){
        int res=0;
        int mid=(left+right)/2;
        int i=left;
        int j=mid+1;
        for (;i<=mid;i++){
            while (j<=right&&num[i]>(long)2*num[j]){
                res+=mid-i+1;
                j++;
            }
        }
        return res;
    }

    public int mergeSort(int[] nums,int[] numsSorted,int left,int right){
        if (left==right) return 0;
        int mid=(left+right)/2;
        int res=mergeSort(nums,numsSorted,left,mid)+
                mergeSort(nums,numsSorted,mid+1,right)+
                findReversePairs(nums,left,right);

        int i=left;
        int j=mid+1;
        int k=left;
        while (i<=mid&&j<=right){
            if (nums[i]<=nums[j]){
                numsSorted[k]=nums[i];
                i++;
            }else{
                numsSorted[k]=nums[j];
                j++;
            }
            k++;
        }

        while(i <= mid) numsSorted[k++] = nums[i++];
        while(j <= right) numsSorted[k++] = nums[j++];

        //将已经排序好的数组放回到nums数组中
        for(int index = left;index <= right;index++)
            nums[index] = numsSorted[index];
        return res;
    }

    public int reversePairs(int[] nums) {
        if (nums.length==0||nums.length==1) return 0;
        int[] numsSorted=new int[nums.length];
        return mergeSort(nums,numsSorted,0, nums.length-1);
    }
}
